package net.xuele.learn.leetcode;

import java.util.*;

/**
 * @Author: yubo
 * @date: 9:36 2020/4/27
 * @Description: 类描述
 */

public class FindDuplicate {

    /**
     * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [1,3,4,2,2]
     * 输出: 2
     * 示例 2:
     * <p>
     * 输入: [3,1,3,4,2]
     * 输出: 3
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * <p>
     * pass
     *
     * @param nums
     * @return
     */
    public static int findDuplicate1(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return nums[i];
            }
        }

        return -1;
    }


    /**
     * 先排序，再比较
     *
     * @param nums
     * @return
     */
    public static int findDuplicate2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
     * <p>
     * 找到所有出现两次的元素。
     * <p>
     * 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
     * <p>
     * 示例：
     * <p>
     * 输入:[1,2,3,4] = 10 ---- [2,2,3,4] == 11 差-1，1-（-1） = 2
     * [4,3,2,7,8,2,3,1] = 30,,,36  == 6  6-x + 5-y = 6 x+y = 5
     * <p>
     * 输出:
     * [2,3]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int length = nums.length;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
        }
        return list;
    }

    /**
     * 升序，记住每个字符的顺序就好了
     * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）
     * <p>
     * 输入：s = "bcabc"
     * 输出："abc"
     *
     * @param s
     * @return
     */
    public static String removeDuplicateLetters(String s) {
        Map<Character, Integer> map = new TreeMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c,i);
            

        }
        return "";
    }

    public static void main(String[] args) {
        Map<Character, Integer> map = new TreeMap<>();
        map.put('z',1);
        map.put('d',2);
        map.put('a',5);
        map.values().forEach(e->{
            System.out.println(e);
        });
    }
}
